Dijkstra’s Algorithm: Single-Source Shortest Path
Dijkstra's Algorithm solves the Single-Source Shortest Path (SSSP) problem for graphs $G=(V, E)$ with non-negative edge weights $w(u, v) \geq 0$. It finds the shortest path from a starting node to all other nodes in the graph.
Core Mechanism (Greedy Approach)
- Initialization: Assign a distance of $D[s]=0$ for the source node $s$, and $D[v]=\infty$ for all other nodes $v$. All nodes are marked as unvisited.
- Iteration: Use a Priority Queue (PQ) to store unvisited nodes, keyed by their current shortest known distance $D[v]$.
- Selection: Iteratively extract the node $u$ with the minimum distance from the PQ. This node is now considered visited, and its distance is finalized.
- Relaxation: For every unvisited neighbor $v$ of $u$, check if a shorter path has been found: if $D[u] + w(u, v) < D[v]$. If true, update $D[v]$ to this new, shorter distance and adjust its priority in the PQ.
Time Complexity Analysis
The efficiency of Dijkstra's algorithm heavily depends on the data structure used for the priority queue and the graph's representation.
| Structure | Initialization | Extraction ($V$ times) | Relaxation ($E$ times) | Total Complexity |
|---|---|---|---|---|
| Priority Queue (Binary Heap) | $O(V)$ | $O(V \log V)$ | $O(E \log V)$ | $O((V + E) \log V)$ |
| Adjacency Matrix | $O(V)$ | $O(V^2)$ | $O(E)$ | $O(V^2)$ |
Constraint: Dijkstra’s Algorithm critically relies on non-negative weights. If negative weights are present, the algorithm fails because its greedy choice (finalizing the minimum distance node) may be incorrect due to subsequent negative edge relaxation.
1. Which statement accurately describes a critical limitation of Dijkstra’s Algorithm?
2. What is the primary data structure used by Dijkstra's algorithm to efficiently select the next node to visit?
3. Dijkstra's algorithm is a classic example of which algorithmic paradigm?